import java.util.ArrayList;
import java.util.List;

public class project {
    public double myPow(double x, int n){
        long N=n;
        return N>0?myPowDfs(x,N):1.0/myPowDfs(x,-N);
    }
    public double myPowDfs(double x,long n){
        if(n==0){
            return 1.0;
        }
        double tmp=myPowDfs(x,n/2);
        return n%2==0?tmp*tmp:tmp*tmp*x;
    }


















    public double myPow1(double x, int n) {
        long N=n;
        return N>0?myPowDfs1(x,N):1.0/myPowDfs1(x,-N);
    }
    public double myPowDfs1(double x,long n){
        if(n==0){
            return 1.0;
        }
        double tmp=myPowDfs1(x,n/2);
        return n%2==0?tmp*tmp:tmp*tmp*x;
    }













    public boolean exist(char[][] board, String word) {
        char[] words=word.toCharArray();
        int row=board.length;
        int col=board[0].length;
        for(int i=0;i<row;i++){
            for(int j=0;j<col;j++){
                if(dfs(board,words,i,j,0)){
                    return true;
                }
            }
        }
        return false;
    }
    public boolean dfs(char[][] str,char[] words,int i,int j,int k){
        if(i<0||i>=str.length||j<0||j>=str[0].length||str[i][j]!=words[k]){
            return false;
        }
        if(k==words.length-1){
            return true;
        }
        str[i][j]='\0';
        boolean bool=dfs(str,words,i+1,j,k+1)||dfs(str,words,i-1,j,k+1)||
                dfs(str,words,i,j+1,k+1)||dfs(str,words,i,j-1,k+1);
        str[i][j]=words[k];
        return bool;
    }

















    public boolean exist1(char[][] board, String word) {
        char[] words=word.toCharArray();
        int row=board.length;
        int col=board[0].length;
        for(int i=0;i<row;i++){
            for(int j=0;j<col;j++){
                if(dfs1(board,words,i,j,0)){
                    return true;
                }
            }
        }
        return false;
    }
    public boolean dfs1(char[][] str,char[] words,int i,int j,int k){
        if(i<0||i==str.length||j<0||j==str[0].length||words[k]!=str[i][j]){
            return false;
        }
        if(k==words.length-1){
            return true;
        }
        str[i][j]='\0';
        boolean bool=dfs1(str,words,i+1,j,k+1)||dfs1(str,words,i-1,j,k+1)||dfs1(str,words,i,j+1,k+1)||dfs1(str,words,i,j-1,k+1);
        str[i][j]=words[k];
        return bool;
    }















    public int[] spiralOrder(int[][] matrix) {
        if(matrix==null||matrix.length==0||matrix[0].length==0){
            return new int[]{};
        }
        int row=matrix.length;
        int col=matrix[0].length;
        int[] arr=new int[row*col];
        int left=0;
        int right=col-1;
        int start=0;
        int end=row-1;
        int k=0;
        while (left<=right&&start<=end){
            for(int i=left;i<=right;i++){
                arr[k++]=matrix[start][i];
            }
            for(int i=start+1;i<=end;i++){
                arr[k++]=matrix[i][right];
            }
            if(left<right&&start<end){
                for(int i=right-1;i>left;i--){
                    arr[k++]=matrix[end][i];
                }
                for(int i=end;i>start;i--){
                    arr[k++]=matrix[i][left];
                }
            }
            left++;
            right--;
            start++;
            end--;
        }
        return arr;
    }















    public List<Integer> spiralOrder1(int[][] matrix) {
        List<Integer> list=new ArrayList<>();
        if(matrix==null||matrix.length==0||matrix[0].length==0){
            return list;
        }
        int row=matrix.length;
        int col=matrix[0].length;
        int left=0;
        int right=col-1;
        int start=0;
        int end=row-1;
        while (left<=right&&start<=end){
            for(int i=left;i<=right;i++){
                list.add(matrix[start][i]);
            }
            for(int i=start+1;i<=end;i++){
                list.add(matrix[i][right]);
            }
            if(left<right&&start<end){
                for(int i=right-1;i>left;i--){
                    list.add(matrix[end][i]);
                }
                for(int i=end;i>start;i--){
                    list.add(matrix[i][left]);
                }
            }
            left++;
            right--;
            start++;
            end--;
        }
        return list;
    }
}
